package com.chj.zhongji.class09.test01;

public class Code03_JumpGame {

	public static int jump(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int jump = 0; // 跳了多少步
		int cur = 0; // jump步内，右边界
		int next = 0;// jump+1步内，右边界
		for (int i = 0; i < arr.length; i++) {
			if (cur < i) {
				jump++;
				cur = next;
			}
			next = Math.max(next, i + arr[i]);
		}
		return jump;
	}

	public static int jump_01(int[] nums) {
		int[] dp = new int[nums.length];// dp[i] 为到达 i 位置的最小跳数
		dp[0] = 0;// 到达下标0的最小跳数是0
		for (int i = 1; i < nums.length; i++) {
			dp[i] = Integer.MAX_VALUE;
			for (int j = 0; j < i; j++) {
				if (i - j <= nums[j]) {
					dp[i] = Math.min(dp[i], dp[j] + 1);
				}
			}
		}
		return dp[nums.length - 1];
	}

	public static int jump_02(int[] nums) {
		int[] dp = new int[nums.length];// dp[i] 为到达 i 位置的最小跳数
		dp[0] = 0;// 到达下标0的最小跳数是0
		for (int i = 1; i < nums.length; i++) {
			dp[i] = Integer.MAX_VALUE;
			for (int j = 0; j < i; j++) {
				if (j + nums[j] >= i) {
					dp[i] = Math.min(dp[i], dp[j] + 1);
				}
			}
		}
		return dp[nums.length - 1];
	}

//	public static int jump_helper(int[] nums, int start, int count, int current_min) {
//		int length = nums.length;
//		if (start >= length - 1) {
////			System.out.println("jump_helper");
////			System.out.print(current_min);
////			System.out.println("jump_helper");
//			current_min = Math.min(current_min, count);
//			return current_min;
//		}
//		for (int steps = 1; steps <= nums[start]; steps++) {
//			current_min = jump_helper(nums, start + steps, count + 1, current_min);
//		}
//		return current_min;
//	}
//
//	public static int jump_03(int[] nums) {
//		int count = 0;
//		int min = nums.length;
//		int res = jump_helper(nums, 0, count, min);
//		return res;
//	}

	public static int jump_helper(int[] nums, int start, int count) {
		int length = nums.length;
		if (start >= length - 1) {
//			System.out.println("count: " + count);
			return count;
		}
		int ans = Integer.MAX_VALUE;
		for (int steps = 1; steps <= nums[start]; steps++) {

			int current_min = jump_helper(nums, start + steps, count + 1);
//			System.out.println("start: " + (start + steps) + " count: " + (count + 1));
//			System.out.println("current_min: " + current_min);
			ans = Math.min(ans, current_min);

//			int current_min = jump_helper(nums, start + steps, count + 1);
//			System.out.println("start: " + (start + steps) + " count: " + (count + 1));
//			System.out.println("current_min: " + current_min);
//			ans = Math.min(ans, current_min);

//			int current_min = jump_helper(nums, start + steps, count + 1);
//			System.out.println("start: " + (start + steps) + " count: " + (count + 1));
//			System.out.println("current_min: " + current_min);
//			ans = Math.min(ans, current_min);
		}
		return ans;
	}

//	https://www.cnblogs.com/Oscar67/p/9285755.html
	public static int jump_03(int[] nums) {
		int res = jump_helper(nums, 0, 0);
		return res;
	}

	// i 是当前位置 temp为当前要跳的步长 ans记录最短路径 step计算下次要跳多远
	public static int rec(int[] nums, int i, int temp, int ans, int step) {
		if (temp == 0)
			return 0;// 跳步为0，返回
		if (i >= nums.length)
			return 0;// i越界，返回
		if (i + temp >= nums.length - 1)// 下一次跳步到或者包含最后一个位置
		{
			ans = step >= ans ? ans : step;
			return ans;
		}
		// 可以重新跳了
		i = temp + i;// 更新i
		temp = 0;// 更新temp
		step++;// 更新步数
		while (temp < nums[i]) {
			ans = rec(nums, i, ++temp, ans, step);
		}

		return ans;
	}

	public static int jump_04(int[] nums) {
		if (nums.length == 0 || nums.length == 1)
			return 0;
		int temp = 0;
		int step = 1;
		int ans = Integer.MAX_VALUE;
		while (temp < nums[0]) {
			ans = rec(nums, 0, ++temp, ans, step);
		}
		return ans;
	}

	public static class Ans {
		int ans;
		int end;

		public Ans(int ans, int end) {
			this.ans = ans;
			this.end = end;
		}
	}

	public static Ans rec_05(int[] nums, int end, int ans) {
		int temp = end;
		ans++;
		for (int i = end - 1; i >= 0; i--) {
			if (nums[i] >= (end - i))// 找到一个最小i，可以直接到达末尾的下标。
				temp = i;
		}
		return new Ans(ans, temp);
	}

	public static int jump_05(int[] nums) {
		int end = nums.length - 1;
		int ans = 0;
		while (end > 0) {
			Ans ends = rec_05(nums, end, ans);
			end = ends.end;
			ans = ends.ans;
		}
		return ans;
	}

	public static int jump_06(int[] nums) {
		int ans = 0;
		int i = 0;
		int left = 0, right = 0;// 在这个区间内计算该选哪个跳步长度
		while (right < nums.length - 1) {
			int next = 0;// 记录下一个要跳去的地方
			for (i = left; i <= right; i++)
				next = Math.max(i + nums[i], next);
			left = right + 1;
			right = next;
			ans++;
		}
		return ans;
	}

	public static int jump_helper_dp(int[] nums) {
		int length = nums.length;
		int ans = Integer.MAX_VALUE;
		int[][] dp = new int[length][length];
		dp[0][0] = 0;
		int steps = nums[0];
		for (int count = 1; count < length; count++) {

			int start = length - 1;
			dp[start][count] = Integer.MAX_VALUE;
			if (start >= count && start <= steps) {
				dp[start][count] = count;
				ans = Math.min(ans, dp[start][count]);
			}
			steps += nums[count];

//			for (int start = 1; start < length; start++) {
//				dp[start][count] = Integer.MAX_VALUE;
//				if (start >= count && start <= steps) {
//					if (start == (length - 1)) {
//						dp[start][count] = count;
//						ans = Math.min(ans, dp[start][count]);
//					}
//				}
//			}
//			steps += nums[count];
		}

		return ans;
	}

//	https://www.cnblogs.com/Oscar67/p/9285755.html
	public static int jump_03_dp(int[] nums) {
		int res = jump_helper_dp(nums);
		return res;
	}

	public static void main(String[] args) {
		{
			int[] arr = { 2, 3, 1, 1, 4, 2, 1 };
			int[] arr2 = { 3, 2, 3, 1, 1, 4 };
			System.out.println(jump(arr));
			System.out.println(jump(arr2));
		}
		{
			int[] arr = { 2, 3, 1, 1, 4, 2, 1 };
			int[] arr2 = { 3, 2, 3, 1, 1, 4 };
			System.out.println(jump_01(arr));
			System.out.println(jump_01(arr2));
		}
		{
			int[] arr = { 2, 3, 1, 1, 4, 2, 1 };
			int[] arr2 = { 3, 2, 3, 1, 1, 4 };
			System.out.println(jump_02(arr));
			System.out.println(jump_02(arr2));
		}
		{
			int[] arr = { 2, 3, 1, 1, 4, 2, 1 };
			int[] arr2 = { 3, 2, 3, 1, 1, 4 };
			int[] arr3 = { 2, 3, 1, 1, 4 };
			System.out.println("jump_03");
			System.out.println(jump_03(arr));
			System.out.println(jump_03(arr2));
			System.out.println(jump_03(arr3));
			System.out.println("jump_03");
		}
		{
			int[] arr = { 2, 3, 1, 1, 4, 2, 1 };
			int[] arr2 = { 3, 2, 3, 1, 1, 4 };
			System.out.println(jump_04(arr));
			System.out.println(jump_04(arr2));
		}
		{
			int[] arr = { 2, 3, 1, 1, 4, 2, 1 };
			int[] arr2 = { 3, 2, 3, 1, 1, 4 };
			System.out.println(jump_05(arr));
			System.out.println(jump_05(arr2));
		}
		{
			int[] arr = { 2, 3, 1, 1, 4, 2, 1 };
			int[] arr2 = { 3, 2, 3, 1, 1, 4 };
			System.out.println(jump_06(arr));
			System.out.println(jump_06(arr2));
		}
		{
			int[] arr = { 2, 3, 1, 1, 4, 2, 1 };
			int[] arr2 = { 3, 2, 3, 1, 1, 4 };
			int[] arr3 = { 2, 3, 1, 1, 4 };
			System.out.println("jump_03_dp");
			System.out.println(jump_03_dp(arr));
			System.out.println(jump_03_dp(arr2));
			System.out.println(jump_03_dp(arr3));
			System.out.println("jump_03_dp");
		}
	}
}
